This invention relates to networks for interconnecting computers, word processors and other devices. Such networks can be divided into two major categories: long haul network, such as the well known ARPA network, and in house networks which operate within a restricted area, such as a building or factory. The latter type is sometimes referred to as a local area network and is the environment of the present invention.
In general, there are three basic topologies for such networks. These are the star, the bus and the ring. The star network is common in computer and communication configurations. The central node of the star may be a computer with many terminals or other peripheral devices connected to it. Another use of the star network is a PBX telephone system.
The bus topology is characterized by a single medium or communication line to which various terminals are connected through a small spur. Bus topology is also common in computer and telecommunication networks.
Ring topology is characterized by the interconnection of stations in a ring. Such an arrangement is common in process instrumentation and control and is currently gaining popularity for communication networks for computers, word processors, etc.
The media or cables that can be used for interconnecting stations in a network are chosen based, in part, upon the topology selected. The choices include twisted pair cable, co-axial cable, twin-axial cable and fiber optic cables. Ring topologies can use any of these cables depending upon the size of the ring and the data transmission frequency involved.
In order for terminals in a ring to communicate with each other, it is necessary to have a protocol often referred to by those skilled in the art as a link level protocol. Many such protocols exist but in the field of local area networks two are particularly important: CSMA-CD and Token Passing.
CSMA-CD (carrier sense multiple access--collision detection) is a link level protocol employed by Xerox Corporation in its Ethernet network which is based on a bus topology. A station connected to a CSMA-CD bus broadcasts a packet of information to all other stations on the bus. The header of the packet contains a destination address of the station for which the packet is intended. Each other station in the system examines the header to see if the packet is addressed to it. If so, it collects the packet, otherwise it rejects it.
A station wishing to send a packet of information listens to the bus and, if it is idle, i.e., no other station is using the bus, then it transmits its packet. If the bus is in use, it defers its transmission until a later time.
Collisions, that is, more than one station attempting to transmit at the same time, can occur with this system. For example, it takes many microseconds for a signal transmitted at one end of the bus to arrive at the other end. Thus, a station may start its transmission unaware of the same event happening elsewhere on the bus some distance away.
In the CSMA-CD protocol these collisions are detected and transmission is suspended until a later time. The attempt to re-transmit is randomized to minimize the probability of further collisions. At the end of a transmission, sufficient time (round trip time on the bus) is allowed for signals to die away before further transmission is permitted.
As a result, the output band width of the CSMA-CD network is reduced due to idle time between transmission windows, the loss due to collisions and the loss due to the randomizing delays provided to avoid further collisions. Also significant is the fact that the lost band width is a function of cable length and speed of transmission. The larger that either of these parameters get the greater the loss of band width incurred.
The token passing protocol, which is employed in the system according to the present invention, has as an ojective the elimination of all collisions during normal operation by introducing a defined order in which the stations may transmit. In this protocol a station may only transmit when it has received a token and there is only one token in the local network. Therefore, only one station may transmit at a time. When the station holding the token is finished transmitting it passes the token on to the next station in the network. In the case of a ring topology there is a natural next station in the ring and thus the token passing protocol is well suited to this topology.
In a ring topology using a token passing protocol every station acts as a repeater, regenerating the signal and transmitting it on to the next station. There are two problems associated with ring topology, namely, phase jitter due to errors in clocking the data into and out of a station and phase delay caused by transmission line delays, etc., around the ring. A ring network must provide circuitry capable of removing data from the ring after it has served its purpose and also for correcting for phase jitter and phase delay to prevent loss of data or synchronization.
The impetus to solve these problems is the significantly better performance of the token passing protocol. At low utilization of the network or when the number of stations on the network are few, the CSMA-CD protocol has a faster response time than token passing. At higher utilization or when there are many stations on the network, however, token passing is faster than CSMA-CD protocol and can support a higher level of traffic for the same network transmission rate. Furthermore, token passing provides a more predictable service in terms of response time because there is a known upper bound on the time it takes for the token to perform a complete circuit of the ring and thus an upper limit on waiting time. In a CSMA-CD protocol, at high utilization, waiting time is unpredictable because collisions can arise repeatedly.
It is accordingly an object of the present invention to provide a method and apparatus for use in a token passing protocol ring network which can effectively dispose of accummulated phase delay around the ring.
A further object of the invention is to provide a method and apparatus for a ring network which can communicate from station to station without losing data or synchronization due to phase jitter or phase delay.
Another object of the invention is to provide a method and apparatus for communicating between stations in a ring network employing decentralized clocking.
Other objects and advantages of the invention will be apparent from the remaining specification.